int compteur=0;
int max(int[] t){// donne le plus grand élèment d'un tableau d'entiers//
	int a,i;
	a=t[0];
	for(i=0;i<t.length;i=i+1){
		if(a<t[i]){a=t[i];}
	}
	return a;
}
int inf(int[] t, int i){
	//donne l'indice du plus petit élèment de t à partir 
	//de l'indice i , i compris
int x=t[i];
int y=i;
for(int j=i+1;j<t.length;j++){
	if(t[j]<x){
		x=t[j];
		y=j;
	}
		
}
return y;
}

void tri_insertion(int[] t){//à la fin t est trié par tri insertion
	int x;
	int k;
for(int i=0;i<t.length-1;i++){
	
	k=inf(t,i+1);	
	if(t[i]>=t[k]){
	x=t[i];	
	t[i]=t[k];
	t[k]=x;	
	}
}
}
void fusion_comp(int[] T,int l,int r,int m,int[] compteur){//rend le tableau T trié quand
	//il est constitué de 2 sous tableaux triés
     // le premier de l'indice l à m et l'autre de m+1 à r avec compteur
	int i,j,k,n1,n2;
	int[]L,R;
	n1=m-l+1;
	n2=r-m;	
	L=new int[n1+1];
	R=new int[n2+1];
	L[n1]=max(T)+1;
	R[n2]=max(T)+1;	
     for(i=0;i<n1;i=i+1)
	  { 	L[i]=T[l+i];}				
     for(i=0;i<n2;i=i+1)
	{R[i]=T[m+1+i];}
	i=0;
	j=0;
	for(k=l;k<=r;k=k+1){		
		compteur[0]=compteur[0]+1;
	if(L[i]<=R[j]){
		T[k]=L[i];
		i=i+1;	
	}
	else{
		T[k]=R[j];
		j=j+1;
	}
	}
}
void fusion(int[] T,int l,int r,int m){//rend le tableau T trié quand
	//il est constitué de 2 sous tableaux triés
     // le premier de l'indice l à m et l'autre de m+1 à r sans compteur   
	int i,j,k,n1,n2;
	int[]L,R;
	n1=m-l+1;
	n2=r-m;	
	L=new int[n1+1];
	R=new int[n2+1];
	L[n1]=max(T)+1;
	R[n2]=max(T)+1;	
     for(i=0;i<n1;i=i+1)
	  { 	L[i]=T[l+i];}				
     for(i=0;i<n2;i=i+1)
	{R[i]=T[m+1+i];}
	i=0;
	j=0;
	for(k=l;k<=r;k=k+1){		
	if(L[i]<=R[j]){
		T[k]=L[i];
		i=i+1;	
	}
	else{
		T[k]=R[j];
		j=j+1;
	}
	}
}
void trifusion_comp(int[] t,int l,int r,int[] compteur){//rend le tableau t trié
	// de l'indice l à l'indice r avec compteur
	int m;
	int i;
	//compteur[0]=compteur[0]+6;	
	if(l<r){
		m=(l+r)/2;
		//compteur[0]=compteur[0]+2;
		trifusion_comp(t,l,m,compteur);
		trifusion_comp(t,m+1,r,compteur);
		fusion_comp(t,l,r,m,compteur);
	}
}
int complexite_recherche(int n){
	if(n==1) return 2;
	else return complexite_recherche(n/2)+2;
}
int complexite_trifusion(int n){
	if(n==1) return 1;
	else return 2*complexite_trifusion(n/2)+n;
}
void trifusion(int[] t,int l,int r){//rend le tableau t trié
	// de l'indice l à l'indice r sans compteur
	compteur=compteur+1;
	int m;
	int i;	
	if(l<r){
		m=(l+r)/2;
		trifusion(t,l,m);
		trifusion(t,m+1,r);
		fusion(t,l,r,m);		
	}
}
void main(){// test les procédures précédentes
	int[] comp={0};	
	println(" ");
	println(" ");
	int nb=128;
	int i;	
	int[] t =new int[nb];
	for(i=0;i<t.length;i=i+1)
{t[i]=(int) (Math.random() * 10000 );
}
println("voilà le tableau initial");
for(i=0;i<t.length;i=i+1)
{print(t[i]);
print("      ");
}
println(" ");
println(" ");
//trifusion(t,0,t.length-1);
tri_insertion(t);
println("voilà le même tableau mais trié par trifusion");
for(i=0;i<t.length;i=i+1)
{print(t[i]);
print("      ");
}
println(" ");
println("nombre d'appels à trifusion: "+compteur);
println("complexite de trifusion: "+complexite_trifusion(t.length));	
//println(comp[0]);
println("nlogn="+t.length*Math.log(t.length)/Math.log(2));
println("nlogn+n="+t.length*(Math.log(t.length)/Math.log(2)+1));
println("n^2="+t.length*t.length);
println(" ");
println("complexité recherche  "+complexite_recherche(t.length));
println("2log(n)+2="+2*(1+Math.log(t.length)/Math.log(2)));
}